// 扫雷游戏：https://leetcode-cn.com/problems/minesweeper/
package main

// 深度优先搜索，简单在了只是扫雷游戏的一步， 且只有 E 到 B 和 数字字符的转换
// 在这道题有意思，相当于是扫雷游戏的其中一步，按一下子的结果
func updateBoard(board [][]byte, click []int) [][]byte {
	// 首先是肯定采用回溯算法，那么如何判断该元素是否访问过？ 只能使用格外的空间进行存储
	// visited := new boolean[rows][cols]
	// 还有斜对角， 所以这里是移动的八个方向
	dir := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
	// 求出行列的大小
	n, m := len(board), len(board[0])
	// 定义深度优先函数
	var dfs func(x, y int)

	dfs = func(x, y int) {
		// 终止条件：越界也终止
		if x < 0 || y < 0 ||
			x >= n || y >= m {
			return
		}
		// 终止条件: 1. 为炸弹不能访问, 除‘E’ 和 炸弹以外的，表示访问过的，也不能访问
		if board[x][y] != 'E' {
			return
		}

		// 处理当前节点： E -> 变为 B 或者 数字
		for _, ac := range dir {
			newX, newY := x+ac[0], y+ac[1]
			if newX >= 0 && newY >= 0 &&
				newX < n && newY < m {
				if board[newX][newY] == 'M' {
					if board[x][y] == 'E' {
						board[x][y] = '1'
					} else {
						board[x][y] = board[x][y] + byte(1)
					}
				}
			}
		}
		// 如果判断了八个角的格子， 这里还保持是 ‘E’， 那就变为 ‘B’
		if board[x][y] == 'E' {
			board[x][y] = 'B'
		}

		//  如果当前节点为 数字字符，不在进行搜索
		if board[x][y] != 'B' {
			return
		}
		// 向下搜索
		for _, ac := range dir {
			newX, NewY := x+ac[0], y+ac[1]
			dfs(newX, NewY)
		}
	}

	// 1. 如果挖到的是地雷，那么将它改为 X，结束游戏
	if board[click[0]][click[1]] == 'M' {
		board[click[0]][click[1]] = 'X'
	} else {
		// 2. 否则递归的挖出来， 修改值
		dfs(click[0], click[1])
	}

	// 3. 返回
	return board
}
